#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

class Solution {
public:
	int numSquares(int n) {
		vector<int> ans(n+1);
		for (int i = 1; i <= n; i++) {
			int current = INT_MAX;
			for (int j = 1; j*j <= i; j++)
				current = min(current, ans[i - j * j]);
			ans[i] = current + 1;
		}
		return ans[n];
	}
};

void main() {
	Solution s;
	s.numSquares(15);
}